\documentclass{ctexart}
\usepackage{graphicx}
\usepackage{listings}
\usepackage{color}

\pagestyle{headings}

\title{BinaryTree和Node设计思路}
\author{谢飞扬 \\ 信息与计算科学 3210104010}
\date{\today}

\definecolor{green}{rgb}{0,0.7,0}
\definecolor{blue}{rgb}{0,0,0.8}
\definecolor{gray}{rgb}{0.95,0.95,0.95}
\definecolor{red}{rgb}{0.6,0,0}

\lstset{
        language=C++,
	basicstyle=\small\ttfamily,	
		keywordstyle=\color{blue}, 
		commentstyle=\color{green},   
		stringstyle=\rmfamily\slshape\color{red}, 
	backgroundcolor=\color{gray},     % 代码块背景颜色
	frame=leftline,						% 代码框形状
	framerule=12pt,
	rulecolor=\color{gray},      % 代码框颜色
	numbers=left,				% 左侧显示行号往左靠, 还可以为right ，或none，即不加行号
		numberstyle=\footnotesize\itshape,	% 行号的样式
		firstnumber=1,
		stepnumber=1,                  	% 若设置为2，则显示行号为1,3,5
		numbersep=5pt,               	% 行号与代码之间的间距
	keepspaces=true, 					
	showtabs=false,                 	% 在字符串中显示制表符
	tabsize=2,                     		% 默认缩进2个字符
	captionpos=b,                   	% 将标题位置设置为底部
	flexiblecolumns=true, 			%
	breaklines=true,                	% 设置自动断行
	breakatwhitespace=false,        	% 设置自动中断是否只发生在空格处
	breakautoindent=true,			%
	breakindent=1em, 			%
	title=\lstname,				%
	xleftmargin=1em,  xrightmargin=0em,     % 设定listing左右的空白
	aboveskip=1ex, belowskip=1ex,
	framextopmargin=0.5pt, framexbottommargin=0.5pt,
        abovecaptionskip=-2pt,belowcaptionskip=3pt,
	% 设定中文冲突，断行，列模式，数学环境输入，listing数字的样式
	extendedchars=false, columns=flexible, mathescape=true,
	texcl=true,
        fontadjust
}

\begin{document}
\maketitle
\section{项目设计思路}
\subsection{继承关系}
Node和BinaryTree是基类，本身没有实现意义，所以用纯虚函数将其变成抽象类，无法实例化。BinarySearchTree是派生类，显然二叉搜索树是一种二叉树，所以从基类BinaryTree继承。AvlTree和SplayTree都是一种自平衡二叉搜索树，所以它们都从派生类BinarySearchTree再做一次继承。BSTNode、AvlNode、SNode都从Node继承。下面是类继承关系图。

\begin{figure}[htbp]
  \centering
  \begin{minipage}{8cm}
    \centering
    \includegraphics[width=8cm,height=1.9cm]  {pic/inherit_graph_0.png}
  \caption{BinaryTree继承图}
  \end{minipage}
  \begin{minipage}{4cm}
    \centering
    \includegraphics[width=4cm,height=1.9cm]  {pic/inherit_graph_1.png}
  \caption{Node继承图}
  \end{minipage}
\end{figure}

\subsection{类成员函数和属性}
基类Node和BinaryTree规定了派生类必须实现的函数。存放数据是Node最基本功能，所以将操作所存放数据的两个方法抽象，而二叉树最基本功能包括了insert、remove和contains，所以将其抽象，并在所有派生类中重新实现纯虚函数。派生类的三个Node作为二叉树节点，都有各自的含参构造函数、析构函数，存放数据的成员属性和指向左右子树的指针，另外AvlNode还保存了当前节点的高度的成员数据。三个二叉树派生类，都有默认构造、拷贝构造、移动构造函数和析构函数，指向根节点的指针root，makeEmpty、isEmpty、findMax、findMin、printTree、clone函数。另外AvlTree有rotate、balance、height、max私有成员函数，SplayTree有rotate、splay和reclaimMemory私有成员函数和nullNode私有成员属性，都是树各自用于自身平衡的。代码总篇幅过长，超过两页，报告仅放入抽象类的代码。
\begin{lstlisting}
/**
 * Node抽象类
 * 存放数据是Node最基本的功能
 */
template <typename DT>
class Node
{
public:
    /// 纯虚函数规范子类的行为，用于为存放数据的私有成员属性提供接口
    virtual DT getData()const =0;
    virtual void setData()=0;
};

/**
 * 二叉树抽象类
 * 二叉树最基本的功能为插入、删除和查找
 * 基于左值和右值提供了两个版本的函数
 */
template <typename DT>
class BinaryTree
{
public:
    virtual void insert(const DT & _data)=0;
    virtual void insert(DT && _data)=0;
    virtual void remove(const DT &  _data)=0;
    virtual bool contains(const DT &  _data)const=0;
};
\end{lstlisting}
\end{document}
